﻿// 0903train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
每个数字最多只能出现2次，超过的需要进行删除
删除某个重复的数字后，其它数字相对位置保持不变
如34533，数字3重复超过2次，需要删除其中一个3，删除第一个3后获得最大数值4533
请返回经过删除操作后的最大的数值，以字符串表示

输出经过删除操作后的最大的数值

输入
34533
输出
4533

输入
5445795045
输出
5479504

先回顾上一道题怎么做的
1 只要使用过，就不再加进来
2 栈顶小于当前，且count>0可以踢

救命，到底什么时候可以踢？踢的时候，那不就是count>1，踢完还有一个可补？
 */
class Solution01
{
public:
    Solution01(string&num_str)
    {
        vector<int>num_count_vec(10);
        for (int i=0; i<num_str.size(); i++)
        {
            int curr = num_str[i] - '0';
            num_count_vec[curr] += 1;
        }
        
        //仔细思考下，什么数是可以踢的，count>2才可以踢
        //而且踢的次数，<count-2 kick_map[curr]=count-2

        unordered_map<int, int>kick_map;
        for (int i=0; i<num_count_vec.size(); i++)
        {
	        if (num_count_vec[i]>2)
	        {
                kick_map[i] = num_count_vec[i] - 2;
	        }
        }

        unordered_map<int, int>used_map;
        vector<int>stack_v;
        for (int i=0; i<num_str.size(); i++)
        {
            int curr = num_str[i] - '0';
            //used==2，不能再进
            if (used_map[curr]==2)
            {
	            
            }
            else
            {
                while (!stack_v.empty()&&stack_v.back()<curr
                    &&kick_map.count(stack_v.back())>0
                    && kick_map.at(stack_v.back())>0
                    )
                {
                    int top_num = stack_v.back();
                    stack_v.pop_back();
                    //更新used，更新kick_map
                    used_map[top_num] -= 1;
                    kick_map[top_num] -= 1;
                }
                stack_v.push_back(curr);
                used_map[curr] += 1;

            }

        }

        string result;
        for (auto&num:stack_v)
        {
            result += to_string(num);
        }
        cout << result;
        //Solution01
    }
};


/*
 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，
在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）

单调栈，如果栈为空，栈顶>=当前，推进去
推坐标进去
如果栈顶比当前小，看看是否能形成凹槽，
1能，计算面积，加到result上面
2不能，把栈顶推出来
 */

class Solution02 {
public:
    int trap(vector<int>& height) {
        vector<int>stack_v;
        int result = 0;
        for (int i=0; i<height.size(); i++)
        {
            if (stack_v.empty())
            {
                stack_v.push_back(i);
            }
            else if (height[stack_v.back()]>height[i])
            {
	            //栈顶>当前，推进去
                stack_v.push_back(i);
            }
            else
            {
	            while (!stack_v.empty()&&height[stack_v.back()]<=height[i])
	            {
                    //栈顶比当前小，不断循环，找凹槽
                    int bottom_i = stack_v.back();
                    stack_v.pop_back();

                    if (!stack_v.empty())
                    {
	                    //左边比bottom高，可以形成凹槽
                        int left_i = stack_v.back();
                        int bottom_h = height[bottom_i];
                        int top_h = min(height[i], height[left_i]);
                        //减掉的1是柱子宽度，柱子左边是坐标
                        int area_w = i - left_i - 1;
                        int area_h = top_h - bottom_h;

                        result += area_w * area_h;
                    }
	            }
                stack_v.push_back(i);
            }

            //for------
        }
        return result;
    }
};


/*
输出边界下标（从 0 开始）和最大蓄水量；如果无法蓄水，则返回 0，此时不返回边界
例如，当山脉为 s=[3,1,2]时，则选取 s[0]和 s[2]作为水库边界
最大蓄水量为 1，此时输出：0 2:1
当山脉 s = [3,2,1]时，不存在合理的边界，此时输出 0

输入描述
一行正整数，用空格隔开，例如输入1 2 3表示 s = [1,2,3]

输出描述
当存在合理的水库边界时，输出左边界、空格、右边界、英文冒号、蓄水量，例如0 2:1
当不存在合理的水库边界时，输出 0

输入
1 9 6 2 5 4 9 3 7
输出
1 6:19
经过分析，选取 s[1]和 s[6] 时，水库蓄水量为 3+7+4+5 = 19 为最大蓄水量

示例2
1 8 6 2 5 4 8 3 7
输出
1 6:15
经过分析，选取 s[1] 和 s[8] 时，水库蓄水量为 15；
同样选取 s[1]和 s[6]时，水库蓄水量也为 15。由于后者下标距离小（为 5），故应选取后者
 */
class Solution03
{
public:
    unordered_map<int, vector<int>>area_map;
    Solution03(vector<int>&height_vec)
    {
        vector<int>stack_v;
        int result = 0, area=0, x=-1, y=-1;

        for (int i=0; i<height_vec.size(); i++)
        {
	        if (stack_v.empty())
	        {
                stack_v.push_back(i);
	        }
            else if (height_vec[stack_v.back()]> height_vec[i])
            {
                stack_v.push_back(i);
            }
            else
            {
                while (!stack_v.empty()&&height_vec[stack_v.back()]<=height_vec[i])
                {
                    int bottom_i = stack_v.back();
                    stack_v.pop_back();

                    //查看是否能形成凹槽
                    if (!stack_v.empty())
                    {
                        int left_i = stack_v.back();
                        int area_h = min(height_vec[i], height_vec[left_i]) - height_vec[bottom_i];
                        int area_w = i - left_i - 1; 

                        area += area_h * area_w;
                        if (area>result)
                        {
                            result = area;
                            x = stack_v.back();
                            y = i;
                        }
                        else if (area==result && (i-stack_v.back())<(y-x))
                        {
                            x = stack_v.back();
                            y = i;
                        }

                    }
                    //while------
                }
                if (stack_v.empty())
                {
	                //说明当前是左边最大的，右边可能形成新的凹槽
                    //重置area
                    area = 0;
                }
                //入栈
                stack_v.push_back(i);
            }
        }

        if (result==0)
        {
            cout << 0;
            return;
        }

        //1 6:19
        cout << x << ' ' << y << ':' << result;

        //Solution03
    }
};

int main()
{
	{
        //1 9 6 2 5 4 9 3 7
        vector<int>height_vec;
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (oh_sstream>>token)
        {
            height_vec.push_back(stoi(token));
        }

        Solution03 solu(height_vec);

        return 0;
	}
	{
        vector<int>height = { 0,1,0,2,1,0,1,3,2,1,2,1 };
        Solution02 solu;
        cout << solu.trap(height);


        return 0;
	}
    //34533
    //5445795045 5479504
    //string num_str = "5445795045";
    string num_str;
    cin >> num_str;
    Solution01 solu(num_str);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
